package domain.tc;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

import domain.tc.Component;
import domain.tc.TCNode;

public class TCClashFinder {

	private Stack<TCNode> ns;
	private Stack<Component> cs;
	private Set<TCNode> visited;
	private List<TCNode> entered;

	public TCClashFinder() {
		ns = new Stack<TCNode>();
		cs = new Stack<Component>();
		visited = new HashSet<TCNode>();
		entered = new ArrayList<TCNode>();
	}

	public Set<TCNode> getVisitedNodes() {
		return this.visited;
	}

	// true if no LessThan edge ever occurred
	public void computeTransitiveClosure(TCNode v) {
		// System.out.println("Computing "+v.toString());
		// boolean hasBadEdge = false;
		visited.add(v);
		// preserve entry order
		if (!entered.contains(v)) {
			entered.add(v);
		}
		v.root = v;
		v.scc = null;
		ns.push(v);
		v.selfloop = false;
		v.hsaved = cs.size();
		for (TCNode w : v.getEdges()) {
			if (w.equals(v)) {
				v.selfloop = true;
			} else {
				// test if it's a bad edge
				// if(v.isBadEdge(w)){
				// hasBadEdge |= true;
				// }
				if (!this.visited.contains(w)) {
					computeTransitiveClosure(w);
				}
				if (w.scc == null) {
					// root v = min entry order of root v and root w
					if (entered.indexOf(w.root) < entered.indexOf(v.root)) {
						v.root = w.root;
						// System.out.println("entered: "+this.entered.toString());
					} else {
						v.root = v.root;
					}
				} else {
					// w has non-empty component
					if (v.hasChild(w) || (!v.hasDescendant(w))) {
						// not a forward edge v,w, meaning w is not a far
						// descendant of v or is a direct descendant of v.
						// System.out.println("push: "+w +" for node "+v);
						cs.push(w.scc);
					}
				}
			}
		}
		// build
		if (v.root.equals(v)) {
			Component C = new Component();
			if (ns.peek().equals(v)) {
				C.successors.clear();
			} else {
				C.successors.clear();
				C.successors.add(C);
			}
			// topological sorts over components, not yet finished, may be buggy
			while (cs.size() != v.hsaved) {
				Component X = cs.pop();
				if (!C.successors.contains(X)) {
					C.successors.add(X);
					C.successors.addAll(X.successors);
				}
			}// end of while
			TCNode w = null;
			while (w == null || !w.equals(v)) {
				w = ns.pop();
				w.scc = C;
				C.content.add(w);
			}
		}
		return;
	}

}
